• 先簡單回顧一下，今天預計分析的題目：
• 24. Swap Nodes in Pairs
• 題目連結：https://leetcode.com/problems/swap-nodes-in-pairs/
• 題目敘述：
  

• 昨天問到，若 input 為 [1,2,3] 那麼 output 為 [2,1,3] 還是 [1,3,2] ?

  • 答案是 [2,1,3]，根據題目的需求，從頭開始讀兩個 Node，將此兩個 Node 做交換，再讀兩個Node，並做交換，以此類推

• 我們使用 迭代/遞迴 來解這個題目

  迭代 Iteration

  • 我們在真正的 Linked list 前，做一個假的 node 作為開頭，稱為 dummy node，dummy node 後面接的資料，才是真正 input 傳進來的 head
  • 所以我們每次執行 while 迴圈都要先判斷， current 後面兩個資料是否都存在
    • 若都存在，我們就將第一個 Node 叫做 first，第二個 Node 叫做 second (這兩個點預計要做交換)
    1. first 即將變成第二個點( second )，所以 first 指向的地方，要變成原本 second 指向的位置
    2. second 即將變成第一個點( first )，所以 second 指向的地方，就會變成 first
    3. 然後將 current 指向交換後的第一個位置 ( second )
    4. 經過上面三個步驟，交換完成，所以 current 會跳到 first 的位置，等待下一次再交換

• python 實作迭代如下：

    class Solution:
        def swapPairs(self, head: ListNode) -> ListNode:
    #       先儲存一個
            dummy = ListNode(0)
            dummy.next = head
            current = dummy

            while current.next != None and current.next.next != None:
    #           first 跟 second 儲存準備交換的 Node
                first = current.next
                second = current.next.next
    #           先把 first Node 指向 second 的下一個Node
                first.next = second.next
    #           先把 second Node 指向 first 的下一個Node 
                second.next = first 
    #           先把 second Node 指向 即將變成第一個點的 second 的下一個Node 
                current.next = second        
    #           把 current 跳到 first 的位置
                current = first
            return dummy.next

遞迴 Recursive

• 根據題目，假設給定一個 linked list：
  

我們需要輸出兩兩交換位置後的 linked list：

• 透過觀察，我們可以發現這個問題可以遞迴分割成小問題：
  給定一個 node *n，*假設 n 的下下個 node 之後的答案我們都知道了，則我們只要將 n 與 n 的下一個 node 交換位置，再接上後面的答案即可。
• 也就是說長度為 6 的 list，我們只要知道後四個節點的答案，就可以得到全部的答案；而要知道後四個節點的答案，只需要先知道後兩個節點的答案，依此類推。
  

利用此遞迴關係，我們不斷將問題化簡成較短的 list ，直到 list 長度為 0 或 1 時，我們終於可以知道答案：

• 當 list 長度為 0，則答案為 None
• 當 list 長度為 1，則答案就是當前這個節點。

綜合以上發現我們可以列出遞迴關係式。為了方便表示，此處用一般的 list 進行表示，並且以 node_i+1 表示 node_i 所指向的下一個節點：

其中，前兩種 case 為終止條件，第三個 case 為遞迴關係。

有了遞迴關係式，我們便可以撰寫程式：

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
#       head 指向第一個位置，若為空，則回傳 None
				if head is None: return None

#       second 指向第二個位置，若為空，則回傳 None        
        second = head.next
        if second is None: return head

#       rest 指向剩下的位置 (就是第二個位置之後)
        rest = second.next
        
#       交換前 [head, second, rest...] -> 交換後 [second, head, rest...]
#       第二個指向第一個，第一個指向剩下的
        second.next = head
        head.next = self.swapPairs(rest)
        
        return second